<?php
/**
 * 收集一些算法
 * 分析算法最混乱的方面大概集中在对数上面。我们已经看到，某些分治算法将以O(nlogn)时间运行。除分治算法外，可将对数最常出现的规律概括为下列一般法则：如果一个算法用常数时间将问题的大小削减为其一部分（一般是1/2），那么该算法就是O(logn)。另一方面，如果使用常数时间只是把问题减少一个常数（如将问题减少1），那么这种算法就是O(n)的。
 *
 * @author tom.wang<tom.wang.sz@qq.com>
 */
class AlgorithmUtil {
	private function __construct() {
		throw new Exception('Can not construct!');
	}
	/**
	 * 冒泡排序（交换排序法之一）
	 * http://zh.wikipedia.org/wiki/%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F
	 * 时间复杂度：О(n²)
	 * “编程复杂度”很低，很容易写出代码
	 * 具有稳定性，这里的稳定性是指原序列中相同元素的相对顺序仍然保持到排序后的序列
	 * 冒泡排序是经过n-1趟子排序完成的，第i趟子排序从第1个数至第n-i个数，若第i个数比后一个数大（则升序，小则降序）则交换两数
	 * 
	 * @param array $arr
	 * @return array
	 */
	public static function bubbleSort($arr) {
		if(!is_array($arr)) return false;
		$count = count($arr);
		if($count <= 1) return $arr;
		for($i = 0; $i < $count; ++$i) {
			//每趟比较前设为false，用于跟踪此趟是否有排序发生
			$sort = false;
			//注意这里$j < $count - $i - 1
			for($j = 0; $j < $count - $i - 1; ++$j) {
				if($arr[$j] > $arr[$j + 1]) {
					$sort = true;
					$tmp = $arr[$j];
					$arr[$j] = $arr[$j + 1];
					$arr[$j + 1] = $tmp;
				}
			}
			if(!$sort) break;
		}
		return $arr;
	}
	
	/**
	 * 快速排序（交换排序法之一）
	 * http://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F
	 * 时间复杂度：О(nlogn，底数为2)
	 * 不具有稳定性
	 *
	 * @param array $arr
	 * @return array
	 */
	public static function quickSort($arr) {
		if(!is_array($arr)) return false;
		$count = count($arr);
		if($count <= 1) return $arr;
		# 这里的key作为一个参考，可以使用其它的数，也可以使用常数
		$key = $arr[0];
		$left_arr = $right_arr = array();
		for($i = 1; $i < $count; ++$i) {
			if($arr[$i] <= $key) $left_arr[] = $arr[$i];
			else $right_arr[] = $arr[$i];
		}
		$left_arr = self::quickSort($left_arr);
		$right_arr = self::quickSort($right_arr);
		return array_merge($left_arr, array($key), $right_arr);
	}
	
	/**
	 * 选择排序（选择排序法之一）
	 * http://zh.wikipedia.org/zh-cn/%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F
	 * 时间复杂度：О(n²)
	 * 每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
	 * 不具有稳定性
	 */
	public static function selectSort($arr) {
		if(!is_array($arr)) return false;
		$count = count($arr);
		if($count <= 1) return $arr;
		for($i = 0; $i < $count - 1; ++$i) {
			$min = $i;
			for($j = $i + 1; $j < $count; ++$j) {
				if($arr[$j] < $arr[$min]) $min = $j;
			}
			$tmp = $arr[$i];
			$arr[$i] = $arr[$min];
			$arr[$min] = $tmp;
		}
		
		return $arr;
	}
	
	/**
	 * 插入排序（插入排序法之一）
	 * http://zh.wikipedia.org/wiki/%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F
	 * 时间复杂度：О(n²)
	 * 对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
	 * 具有稳定性
	 */
	public static function insertSort($arr) {
		if(!is_array($arr)) return false;
		$count = count($arr);
		if($count <= 1) return $arr;
		//先将第一个元素放到已排序数组
		$sortArr = array($arr[0]);
		for($i = 1; $i < $count; ++$i) {
			$countSort = count($sortArr);
			$offset = -1;
			for($j = $countSort - 1; $j >= 0; --$j) {
				if($sortArr[$j] <= $arr[$i]) {
					$offset = $j;
					break; //找到必须break
				}
			}
			//将元素插入到适当位置,注意这里$offset + 1
			array_splice($sortArr, $offset + 1, 0, $arr[$i]);
		}
		
		return $sortArr;
	}
	
	/**
	 * 桶式排序
	 * 第一轮按个位数排序、第二轮按十位数排序，依此类推。
	 */
	public static function bucketSort($arr) {
		if(!is_array($arr)) return false;
		if(1 == count($arr)) return $arr;
		$bucket = array();
		foreach($arr as $val) {
			
		}
	}
	
	/**
	 * 二分查找
	 * 算法复杂度：O(logn)
	 *
	 * @param array $input
	 * @param mixed $search
	 *
	 * @return int
	 */
	public static function binarySearch($input, $search) {
		if(!$input || !is_array($input)) return false;
		$low = 0;
		$high = count($input) - 1;
		# 这里假设$input是已经排序好的数组
		while($high >= $low) {
			$middle = ceil(($low + $high) / 2);
			if($input[$middle] === $search) {
				return $middle;
			} elseif($input[$middle] < $search) {
				$low = $middle + 1;
			} else {
				$high = $middle - 1;
			}
		}
		return false;
	}
	
	/**
	 * 约瑟夫问题
	 * 一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。
	 *
	 * @param array $input
	 * @param int $start
	 * @param int $step
	 *
	 * @return 
	 */
	public static function josephus($input, $start = 1, $step = 5) {
		# 这里的$start -= 1是将人类习惯以1开始计数转换为数组中的以0开始计数。
		# 每一轮必有一个猴子出圈。
		for($i = count($input), $start -= 1; $i > 0; --$i) {
			$start = ($start + $step - 1) % $i;
			# array_splice、array_slice参数都是offset、length，并且包括offset的位置。
			# array_splice中的数组是按引用传递的，array_slice则不是。
			$arr = array_splice($input, $start, 1);
			echo $arr[0] . '<br />';
		}
	}
	
	/**
	 * 斐波那契数列
	 * f(x+2) = f(x+1) + f(x)
	 * (0)1 (1)1 (2)2 (3)3 (4)5 (5)8 (6)13 (7)21 ...
	 */
	public static function fibonacci($num) {
		# 这里用一个static变量缓存已经计算过的数据，这样速度快很多
		static $values = array();
		if(isset($values[$num])) return $values[$num];
		if($num <= 1) return $values[$num] = 1;
		else
			# 在计算$num - 1的值时，其实也计算了$num - 2, $num - 3, $num - 4 ......的值
			return $values[$num] = self::fibonacci($num - 1) + self::fibonacci($num - 2);
	}
	
	/**
	 * 计算一组数中能得到最大和的序列
	 * 如 [3 -2 3 4 -1 5] -3
	 */
	public static function maxSeqSum($datas) {
		$max = $tag = 0;
		$count = count($datas);
		for($i = 0; $i < $count; ++$i) {
			$tag += $datas[$i];
			if($tag > $max) $max = $tag;
			if($tag < 0) $tag = 0;
		}
		
		return $max;
	}
	
	/**
	 * 找出两个自然数的最大公约数（或最大公因数）
	 *
	 * 如果有一个自然数a能被自然数b整除，则称a为b的倍数，b为a的约数。几个自然数公有的约数，叫做这几个自然数的公约数。公约数中最大的一个公约数，称为这几个自然数的最大公约数。
	 * 例: 在2、4、6中，2就是2，4，6的最大公约数。
	 * 早在公元前300年左右，欧几里得就在他的著作《几何原本》中给出了高效的解法——辗转相除法。辗转相除法使用到的原理很聪明也很简单，假设用f（x, y）表示x，y的最大公约数，取k = x/y，b = x%y，则x = ky + b，如果一个数能够同时整除x和y，则必能同时整除b和y；而能够同时整除b和y的数也必能同时整除x和y，即x和y的公约数与b和y的公约数是相同的，其最大公约数也是相同的，则有f（x, y）= f（y, x%y）（y > 0），如此便可把原问题转化为求两个更小数的最大公约数，直到其中一个数为0，剩下的另外一个数就是两者最大的公约数。
	 */
	public static function gcd($x, $y) {
		if($x < $y) self::switchVal($x, $y, 2);
		while($y > 0) {
			$tmp = $x % $y;
			$x = $y;
			$y = $tmp;
		}
		
		return $x;
	}
	
	/**
	 * 不用第三个变量，实现两个变量值互换
	 *
	 * @param mixed $val1
	 * @param mixed $val2
	 *
	 * @return 
	 */
	public static function switchVal(&$val1, &$val2, $way = 1) {
		# method 1
		# switch compare loose
		switch(intval($way)) {
			case 1:
				list($val1, $val2) = array($val2, $val1);
				break;
			case 2:
				$val1 = $val1 ^ $val2;
				$val2 = $val2 ^ $val1;
				$val1 = $val1 ^ $val2;
				break;
			case 3:
				//better to use ^ , use this may decrease the pricise
				$val1 = $val1 + $val2;
				$val2 = $val1 - $val2;
				$val1 = $val1 - $val2;
				break;
		}
	}
}
?>